The Internet Protocol was originally developed with the assumption that users, each of which is assigned a unique Internet address, would be connected to the network at fixed locations. However, with the rapid acceptance of portable and handheld devices amongst consumers, the movement or migration of users about an individual network is typically the norm rather than the exception. As a result, the implicit design assumptions of the Internet Protocol are violated by this type of usage.
Radio access networks provide one of the most important network access technologies to extend the reach of the Internet to the mobile population, allowing mobile terminals to communicate with others at anytime, anywhere. Over the years, various mobility models have been proposed to support both wide-area macro-mobility and local-area micro-mobility, with an emphasis on primarily mobile-to-fixed and fixed-to-mobile network communication. These include for example Cellular IP, HAWAII, Mobile IPv4 and IPv6. These solutions, however, do not provide optimal routing paths for mobile-to-mobile communications because of the common requirement of routing IP packets through an anchor point in the network. However, as small and portable network devices rapidly penetrate the market, optimized mobile-to-mobile communication in metropolitan areas (e.g. Ottawa, Toronto) is crucial for the next generation of wireless Internet applications.
FIG. 1 is an example of a typical system which allows mobile terminals to access the Internet. The system consists of two all-IP radio access networks (RANs) 100, 140 providing access services to two metropolitan areas such as Ottawa and Toronto. An all-IP RAN is a pure packet switched network based on the Internet Protocol (IP). Each RAN 100, 140 consists of radio-related network elements called radio access nodes (RNs) 110 that are attached to an infrastructure of cooperative interconnected IP packet routers 106. The radio access nodes (RNs) 110 are radio access points that provide wireless access services to mobile terminals (MTs) 105, 109 within the coverage area of each radio access node. The packet routers 106 interconnect the radio access nodes (RNs) 110 to form the infrastructure for data transportation within each RAN 100, 140. Various gateways and/or network edge routers (NERs) 107 connect each RAN 100, 140 with an Internet backbone 103 comprising a set of routers 119, thereby enabling the mobile terminals (MTs) 105, 109 to access a broad range of network services available throughout the Internet.
A mobile terminal 105, 109 can establish a connection to the Internet 103 through the radio access node (RN) 110 serving the mobile terminal, a sequence of IP routers 106 leading to a network edge router (NER) 107 which is, in turn, directly connected to the Internet backbone 103. The radio access node (RN) 110 serving the mobile terminal is its “point of access” to the network. Because a mobile terminal is by definition mobile, a mobile terminal connecting to the Internet via a wireless interface may change its point of access. This may occur, for example, if the mobile terminal initiates an Internet sessions from different locations or because the mobile terminal is moving while an active data session is ongoing.
Typically, location information is encoded in an Internet address (i.e. IP address). Therefore, in conventional systems, a mobile terminal must be located on the network at the location indicated by its IP address in order to receive IP packets. In such systems, a mobile terminal may need to change its IP address whenever it changes its point of access to the network for it to not lose its ability to communicate. Likewise, if a mobile terminal moves from one network to another, convention dictates that its IP address must also change.
Most user mobility can be assumed to be local to a RAN domain. For example, in FIG. 1 most user mobility would occur within the Ottawa RAN 100 or within the Toronto RAN 140. Each RAN must, therefore, provide efficient mobility support for forwarding data packets that originate from and are destined to mobile users who move within such a RAN. The mobile users in a RAN will include both local users whose home domain is the current network (e.g. the RAN in Ottawa) and roaming users whose home domain is another network (e.g. the RAN in Toronto). Mobility within a single radio access network (RAN) is referred to as micro-mobility while mobility between separate radio access networks is referred to as macro-mobility. Examples of micro-mobility and macro-mobility are indicated at 120, 122 of FIG. 1, respectively.
Consider now FIG. 2 which shows an example system consisting of a single all-IP RAN 200 connected to an Internet backbone 203 via a network edge router (NER) 207. The RAN 200 and the Internet backbone 203 each consist of a plurality of cooperative interconnected routers 206, 209 to form the infrastructure for data transportation in the internetwork. A fixed host (FH) 208 is located outside of the RAN 200 and is connected to the Internet backbone 203 via an access network which is not shown. The RAN 200 has a first radio access node (RN.a) 210 which provides wireless access services to mobile terminals, such as a mobile terminal (MT) 205, in the coverage area of the radio access node (RN.a) 210. Similarly, the RAN 200 has a second radio access node (RN.b) 230 which provides wireless access services to mobile terminals in its respective coverage area.
Suppose, for example, that the mobile terminal (MT) 205 were to leave the coverage area of RN.a 210 and enter the coverage area of RN.b 230. Because the IP addresses are based on location, this necessitates a change in the IP address. However, a change in the IP address would make it impossible for the mobile terminal (MT) 205 to maintain active transport and higher-layer connections (e.g. TCP/UDP sessions) because they do not allow for IP addresses to change during an active session. A change of access point during active data transmission or reception is commonly referred to as a “handoff”. During or immediately after a handoff, physical layer losses may occur due to delayed propagation of new location information. These losses need to be minimized in order to avoid a degradation of service quality as handoffs become more and more frequent.
A solution is needed, therefore, whereby a mobile host does not lose any of its sessions due to a handoff. Specifically, some sort of mechanism is required to ensure that packets addressed to moving hosts are successfully delivered with high probability.
Background on IP Routing
An interconnected router system, such as that depicted in FIG. 2, forms the architectural basis for all networks and handles all traffic except for direct delivery from one terminal (or host) to another. Essentially, a data packet travels from router to router until it reaches a router that attaches directly to a node providing service to the final destination. Except for destinations on directly attached networks, terminals (fixed or mobile) pass all IP traffic to routers which forward packets on toward their final destinations.
The conventional IP routing algorithm employs an Internet routing table (IP routing table) on each router that stores information about possible destinations and how to reach them. Whenever the routing IP software in a host or router needs to transmit a data packet, it consults the routing table to decide where to send the data packet. Typically, a routing table contains data pairs (N,R) where N is the IP prefix or IP address of a destination and R is the IP address of the ‘next’ router along the path to network N. As such, router R is called the next-hop and the idea of using a routing table to store a next-hop for each destination is called “next-hop routing”.
The routing table in a router R only specifies one step along the path from R to a destination network N i.e. the router does not know the complete path to a destination. Furthermore, to hide information, keep routing tables small and make routing decisions efficient, IP routing software only keeps information about destination network addresses, not about individual host addresses. Conventionally, most routing has been based on networks and not on individual hosts to minimize information stored in routing tables; most IP routing software implementations do however allow per-host routes to be specified.
When a data packet arrives at a router, the network interface software delivers it to the IP software. Two scenarios are possible. The data packet could have reached its final destination or it may need to travel further. As with hosts, if the data packet destination IP address matches the router's own IP address, the IP software passes the data packet to higher-level protocol software for processing. However, if the data packet has not reached its final destination, IP routes the data packet using the standard IP routing algorithm and information contained in the local routing table.
Specifically, when IP software looks up a route, the algorithm produces the ingress interface of the next node (i.e. the address of the next-hop router) to which the data packet should be sent. IP then passes the data packet and the next hop address to network interface software. Finally, transmission of the data packet from one machine to the next involves encapsulating the data packet in a physical frame, mapping the next-hop address to a physical address, and then sending the frame using underlying hardware. It is important to note that the Internet routing algorithm is table-driven and uses only IP addresses.
In general, establishing routes in a routing table will involve some form of initialization and update. Each router in a network must establish an initial set of routes when it boots up and it must also update the routing table as routes change. In small slowly changing networks, network managers can establish and modify routes manually. Most networks, however, are not static. Connections fail and are later replaced. Automated methods are therefore needed.
The purpose of an automated routing propagation algorithm is not merely to find a set of routes, but to continually update the information as well. To automate the task of keeping network reachability information accurate, routers within a network may communicate with one another exchanging network reachability data or network routing information from which reachability can be deduced. Interior Gateway Protocol or IGP is a generic term used to refer to an algorithm that routers within an autonomous network use when they exchange routing information.
To exchange routing information, routers usually use one of two basic types of algorithms i.e. distance-vector or Shortest Path First (SPF). The chief disadvantage of distance-vector algorithms is that they perform a distributed shortest path computation that may not converge if the status of network connections change continually i.e. the algorithm does not scale well.
The primary alternative to distance-vector algorithms is a class of route propagation algorithms known as link-state, Shortest Path First or SPF. The SPF algorithm requires each participating router to have complete topology information. Additionally, instead of sending messages that contain lists of destinations as in the distance-vector case, a router participating in an SPF algorithm performs two tasks: firstly, it actively tests the status of all neighboring routers and, secondly, it periodically propagates this link status information to all other routers.
For example, to test the status of a directly connected neighbor, a router periodically exchanges short messages that ask whether the neighbor is alive and reachable. If the neighbor replies, the link between them is said to be ‘up’. Otherwise the link is said to be “down”. To update all other routers, each router will periodically broadcasts a ‘link status message’ that lists the state of each of its links. Note that the status messages does not specify routes—it simply reports whether communication is possible between router pairs. Protocol software in the routers will arrange to deliver a copy of each link status message to all participating routers.
When a link status message arrives at a router, it uses the information to update its internal map of the network by marking links ‘up’ or ‘down’. Whenever a link status changes, the router recomputes routes by applying the well known Dijkstra shortest path algorithm. Dijkstra's algorithm computes the shortest paths to all destinations from a single source.
One of the most widely used IGPs is the Routing Information Protocol (RIP). The underlying RIP protocol is a straightforward implementation of distance-vector routing algorithm for local networks. An alternative IGP that uses the SPF algorithm and provides better scalability is called Open SPF or OSPF. OSPF sends ‘hello’ messages on each link periodically to establish and test neighbor reachability. Routers then exchange OSPF database description messages to initialize their network topology database. After exchanging database description messages with a neighbor, a router may request the neighbor to supply updated information by sending a ‘link status request’ message. Routers respond by broadcasting the status of links with a ‘link status update’ message.